package designpatterns.strategy;

import java.util.ArrayList;
import java.util.Arrays;

public class QuickSort extends GeneralSort {
	
		
	@Override
	public ArrayList<Integer> sort(ArrayList<Integer> data) {
		internalData = data.toArray(new Integer[data.size()]);
		
		ExecTime = System.currentTimeMillis();
		quicksort (0, this.internalData.length - 1);
		ExecTime = System.currentTimeMillis() - ExecTime;
				
		return new ArrayList <Integer> (Arrays.asList(internalData));
	}

	private void quicksort(int start, int end) {
		if (start >= end)
			return;
		else {
			int pivotPos = findPivot(start, end);
						
			quicksort(start, pivotPos - 1);
			quicksort(pivotPos + 1, end);
		}
	    	    
    }

	private int findPivot(int start, int end) {
		int pivot = (start + end) / 2;
		int pivotPos = start;
			
		swap(pivot, end);
		
		for (int i = start; i < end ; i++) {
			if (internalData[i] <= internalData[end]) {
				swap(pivotPos, i);
				pivotPos++;
			}
		}
		
		swap(pivotPos, end);
		
		return pivotPos;
    }


	@Override
    public String getName() {
	    // TODO Auto-generated method stub
	    return "Quicksort " + isSorted();
    }
	
	

}
